{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Base case: factorial(0) = 1\n",
      "factorial(1) = 1 * factorial(0) = 1\n",
      "factorial(2) = 2 * factorial(1) = 2\n",
      "factorial(3) = 3 * factorial(2) = 6\n",
      "factorial(4) = 4 * factorial(3) = 24\n",
      "factorial(5) = 5 * factorial(4) = 120\n",
      "\n",
      "5 的阶乘是: 120\n"
     ]
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    # 基本情况：当 n 为 0 时，阶乘为 1\n",
    "    if n == 0:\n",
    "        print(f\"Base case: factorial({n}) = 1\")\n",
    "        return 1\n",
    "    # 递归情况：n! = n * (n-1)!\n",
    "    else:\n",
    "        result = n * factorial(n - 1)\n",
    "        print(f\"factorial({n}) = {n} * factorial({n-1}) = {result}\")\n",
    "        return result\n",
    "\n",
    "# 计算 5 的阶乘\n",
    "result = factorial(5)\n",
    "print(\"\\n5 的阶乘是:\", result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "需要的硬币数量： {5: 2, 2: 1, 1: 1}\n"
     ]
    }
   ],
   "source": [
    "def greedy_coin_change(coins, amount):\n",
    "    coins.sort(reverse=True)  # 按面额从大到小排序\n",
    "    num_coins = {coin: 0 for coin in coins}\n",
    "\n",
    "    for coin in coins:\n",
    "        while amount >= coin:\n",
    "            amount -= coin\n",
    "            num_coins[coin] += 1\n",
    "\n",
    "    return num_coins if amount == 0 else None\n",
    "\n",
    "coins = [1, 2, 5]\n",
    "amount = 13\n",
    "result = greedy_coin_change(coins, amount)\n",
    "\n",
    "if result:\n",
    "    print(\"需要的硬币数量：\", result)\n",
    "else:\n",
    "    print(\"无法凑成目标金额\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
